#ifndef __TEMPARENA_H_
#define __TEMPARENA_H_

#include <sstream>
#include "util.h"

struct FullException {};

/*
inline void * operator new (size_t size, TempArena & arena) {
  // cout << "Temparena new" << endl;
  return arena.allocate(size); }
inline void operator delete (void * p, TempArena & arena) {}
*/

const uint64 kDeletedBit = (1ull << 63);
const uint64 kGenerationBits = kDeletedBit - 1;

// store for temporary hash maps from uint64 to uint64 
// (or anything that fits inside a uint64) 
// Call Clear() to empty the whole thing. 
// If fallable is set to true, throws an exception when it gets full. 
//  otherwise, reorganizes and possibly grows, removing all keys with 0 values.
// Use: Create one TempHashArena per thread, and then create TempHash objects
//   that are backed by it. 
struct TempHashArena {
  struct Cell {
    uint64 generation_; // high bit set means deleted
    uint64 key_;
    uint64 value_;
    string ToString() {
      ostringstream o;
      o << generation_ << " " << key_ << " " << value_;
      return o.str();
    }
  };
  uint64 lg_size_;
  uint64 size_; // in cells
  uint64 mask_;
  Cell *data_;
  uint64 next_id_;
  bool fallable_;
  uint64 generation_;
  bool inited_;
  bool needs_reorg_;
  set<uint64> ids_;
  
  TempHashArena() { inited_ = false; data_ = NULL; }
  
  void Init(uint64 lg_size, bool fallable = true) {
    next_id_ = 1; // 0 is used to ask for a new id
    ids_.clear();
    inited_ = true;
    fallable_ = fallable;
    ReInit(lg_size);
  }

  void ReInit(uint64 lg_size) {
    CHECK(lg_size >= 10);
    lg_size_ = lg_size;
    size_ = 1 << lg_size;
    mask_ = size_ - 1; CHECK(mask_ != 0);
    data_ = new Cell[size_];
    generation_ = 1;
    for (uint64 i=0; i<size_; i++) data_[i].generation_ = 0;
    needs_reorg_ = false;
  }
  
  void Clear() { 
    generation_++; 
    needs_reorg_ = false;
    ids_.clear();
    next_id_ = 1;
  }
  
  void ClaimID(uint64 id) { 
    CHECK(!(ids_ % id)); 
    ids_.insert(id); }
  
  Cell * CellLookup(uint64 key, bool *insert) {
    CHECK(inited_);
    if (insert && needs_reorg_) Reorg();
    uint64 pos = key & mask_;
    uint64 step = 0;
    Cell * insert_cell = NULL;
    while (1) {
      Cell & c = data_[pos];
      if (c.generation_ == generation_ && c.key_ == key) {
	// found it
	if (insert) *insert = false; 
	return &c; 
      } else if (c.generation_ == generation_) {
	// correct generation - incorrect key
      } else if ((c.generation_ & kGenerationBits) == generation_) {
	// deleted cell for this generation
	if (!insert_cell) insert_cell = &c;
      } else {
	// different generation
	if (!insert_cell) insert_cell = &c;
	break;
      }
      step++;
      pos = (pos + step) & mask_;
    }
    if (step > 50 && !needs_reorg_) needs_reorg_ = true;

    if (!insert) return NULL;
    *insert = true;
    insert_cell->generation_ = generation_;
    insert_cell->key_ = key;
    insert_cell->value_ = 0;
    return insert_cell;
  }
  uint64 * Lookup(uint64 key, bool *insert) {
    Cell * look = CellLookup(key, insert);
    if (!look) return NULL;
    return &look->value_;
  }
  void Delete(uint64 key) {
    Cell * look = CellLookup(key, NULL);
    // cout << "TempHashArena::Delete look=" << (void*) look << endl;
    if (look) {
      //cout << "old cell:" << look->ToString() << endl;
      look->generation_ |= kDeletedBit;
      //cout << "new cell:" << look->ToString() << endl;
    }
  }
  void Reorg() {
    cout << "Reorganizing TempHashArena" << endl;
    if (fallable_) throw FullException();
    uint64 full_count = 0;
    uint64 deleted_count = 0;
    for (uint64 i=0; i<size_; i++) {
      Cell & c = data_[i];
      if (c.generation_ == generation_) full_count++;
      if (c.generation_ == (generation_ | kDeletedBit)) deleted_count++;
    }
    bool increase_size = ((deleted_count * 2) < full_count);
    Resize(increase_size ? (lg_size_ + 1) : lg_size_);
  }
  void Resize(uint64 new_lg_size) {
    cout << "Resizing TempHashArena " 
	 << "old_lg_size_: " << lg_size_
	 << " new_lg_size_: " << new_lg_size << endl;
    Cell * old_data = data_;
    uint64 old_size = size_;
    uint64 old_generation = generation_;
    ReInit(new_lg_size);
    for (uint64 i=0; i<old_size; i++) {
      Cell & c = old_data[i];
      bool insert;
      if (c.generation_ == old_generation) {
	*Lookup(c.key_, &insert) = c.value_;
      }
    }
    delete [] old_data;
  }
};

const uint64 kDeletedValue = 0x239282fea3285291ull;
const uint64 kDefaultValue = 0ull;

// V must fit in a uint64
template<class K, class V> struct TempHash {
  TempHash() { inited_ = false; base_ = NULL;}

  uint64 FP(K k) { return Fingerprint((uint64)k, id_);}

  void Init(TempHashArena *a, uint64 id) {
    inited_ = true;
    CHECK(sizeof(V) <= sizeof(uint64));
    arena_ = a;
    id_ = id;
    if (!id_) id_ = (a->next_id_)++;
    arena_->ClaimID(id_); }
  
  void AddBase(TempHash<K, V> *base) {
    base_ = base; }


  // void clear() { id_ = arena_->GetId(); }
  
  V & operator [] (K k) {
    bool inserted;
    V * look = Lookup(k, &inserted);
    if (inserted) *look = kDefaultValue;
    return *look; }
  
  V * operator % (K k) {
    return Lookup(k, NULL); }

  void Delete(K k) {
    CHECK(inited_);
    if (base_) {
      (*this)[k] = (V)kDeletedValue;
      return;
    }
    arena_->Delete(FP(k));
  }

  V * Lookup(K key, bool *insert) { 
    CHECK(inited_);
    V * look = (V *)arena_->Lookup(FP(key), insert);
    if (!base_) return look;
    if (!insert) {
      if (!look) return base_->Lookup(key, NULL);
      if ((uint64)(*look) == kDeletedValue) return NULL;
      return look;
    }
    // there is a base and we are inserting if necessary
    if (*insert) {
      V * look_base = base_->Lookup(key, NULL);
      if (look_base) {
	*look = *look_base;
	*insert = false;
      }
      return look;
    } else {
      if ((uint64)(*look) == kDeletedValue) {
	*look = kDefaultValue;
	*insert = true;
      }
      return look;
    }
  }

  
  TempHashArena *arena_;
  uint64 id_;
  bool inited_;
  TempHash<K, V> *base_;
};

int temparena_main();

/*
struct TempArena {
  uint64 * data_;
  uint64 * current_;
  uint64 * end_;
  
  void * allocate (size_t t) {
    // cout << "allocate " << t << endl;
    uint64 * ret = current_;
    uint64 num_words = (t + sizeof(uint64) - 1) / sizeof(uint64);
    current_ += num_words;
    if (current_ > end_) throw FullException();
    return ret;
  }
  void deallocate( void * p) {}

  TempArena(uint64 word_size) {
    data_ = new uint64[word_size];
    current_ = data_;
    end_ = data_ + word_size;
  }
  void Clear() {
    current_ = data_;
  }
  bool NeedsFree() { return false; }  
};
*/

#endif
